package slist;

import java.util.Scanner;

public class MySingleList {
    /**
     * 节点内部类
     */
    static class ListNode {
        int value;
        ListNode next;

        // 注意：为了输入数据并且测试方便，使用了构造方法，而不使用创建链表的方方法去先创建一个链表
        public ListNode(int value) {
            this.value = value;
        }
    }

    private ListNode head; //默认初始化为null。

//    // 创建链表
//    public void createList() {
//        Scanner scanner = new Scanner(System.in);
//        this.head = new ListNode();
//        this.head.value = scanner.nextInt();
//        this.head.next = null;
//
//        ListNode cur = this.head;
//
//        while(!scanner.hasNext("exit")) {
//            ListNode newNode = new ListNode();
//            newNode.value = scanner.nextInt();
//            newNode.next = null;
//
//            cur.next = newNode;
//            cur = cur.next;
//        }
//    }

    // 打印链表
    public void display() {
        ListNode cur = this.head;
        while(cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
    }

    // 销毁链表
    public void clear() {
        // Java中单链表可以直接把head置空，第一个节点置空后，被JVM回收
        // 第二个节点就没有引用再指向它，所以也被回收，所以
        // JVM依次从前往后回收链表的节点，从而实现链表的销毁
        this.head = null;
    }

    //头插法
    public void addFirst(int data) {
        // 创建了新节点，并完成初始化
        ListNode newNode = new ListNode(data);
        newNode.next = null;

        // 1、新节点连接在第一个节点的前面
        // 2、更新head头节点
        newNode.next = this.head;
        this.head = newNode;
    }

    //尾插法
    public void addLast(int data) {
        // 1 给对象分配空间
        ListNode newNode = new ListNode(data);
        newNode.next = null;

        // 2 空链表
        if(this.head == null) {
            this.head = newNode;
        }
        // 3 链表至少有1个节点
        else {
            ListNode cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }

            // 4 找到尾节点,插入数据
            //出循环cur.next == null，即cur是最后一个节点
            cur.next = newNode;
        }
    }

    //任意位置插入,第一个数据节点为1号下标
    public void addPos(int pos,int data) {
//        //法一：
//        //1、头插
//        if(pos == 1) {
//            addFirst(data);
//        }else {
//            //2、尾插+任意插
//            // 注意:如果是带头节点，可以j从0开始计算，prev从头节点开始
//            // 就不需要单独考虑头插的问题，下面代码就可完成任意位置插入
//            ListNode newNode = new ListNode(data);
//            newNode.next = null;
//
//            int i = 1;
//            ListNode prev = this.head;
//            //理解: 如果位置是合法的, 那么出循环后i=pos-1, i表示的是第i个
//            // 所以此时prev是第i个即第pos-1个节点
//            while (prev != null && i<pos-1) {
//                prev = prev.next;
//                ++i;
//            }
//
//            if(prev == null || i > pos-1) {
//                System.out.println("位置不合法");
//                return;
//            }
//
//            newNode.next = prev.next;
//            prev.next = newNode;
//        }

//        //法二
//        // 1、先单独考虑不合法位置
//        if(pos<1 || pos > this.size()+1) {
//            System.out.println("pos位置不合法");
//            //可以设置一个异常，然后抛出
//        }
//        // 2、合法
//        else {
//            // 2.1、头插
//            if(pos == 1) {
//                addFirst(data);
//            } else {     //2.2、尾插和中间位置插入
//                ListNode newNode = new ListNode(data);
//                newNode.next = null;
//
//                int i = 1;
//                ListNode cur = this.head;
//                while(cur.next!=null && i<pos-1){ //i<pos-1的目的是，出循环后能找到pos位置的前一个阶节点位置的地址
//                    i++;
//                    cur = cur.next;
//                }
//
//                // 走到这里说明下标合法，且cur不为null，所以找到了pos位置的前一个
//                newNode.next = cur.next;
//                cur.next = newNode;
//            }
//        }

        //法三：方便简单
        // 1 合法性
        if(pos < 1 || pos > this.size()+1) {
            System.out.println("位置不合法");
        }

        // 2 头插
        if(pos == 1) {
            addFirst(data);
        }
        // 3 尾插
        else if (pos == this.size()+1) {
            addLast(data);
        }
        // 4 普通位置插入
        else {
            ListNode prev = findPosPrevNode(pos);
            ListNode newNode = new ListNode(data);

            newNode.next = prev.next;
            prev.next = newNode;
        }
    }
    //找到pos的前一个节点
    private ListNode findPosPrevNode(int pos) {
        ListNode prev = this.head;
        // 注意:比如pos=3,循环只执行一次,所以找到第二个节点
        while (pos-1> 1) {
            pos--;
            prev = prev.next;
        }
        return prev;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if(cur.value == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        //法一：一个一个判断
        //1、空链表
        if(this.head == null) {
            return;
        }
        // 2、判断第一个节点
        if(this.head.value == key) {
            this.head = this.head.next;
        }else {
            ListNode cur = this.head;
            //3、判断第二个到最后一个节点
            while (cur.next != null) {
                if(cur.next.value == key) {
                    cur.next = cur.next.next;
                    break;
                }

                cur = cur.next;
            }
        }
//        //法二：
//        // 1 空链表
//        if(this.head == null) {
//            return;
//        }
//        // 2 判断第一个节点的value是否等于key
//        if(this.head.value == key) {
//            this.head = this.head.next;
//            return;
//        }
//        // 3 findPrevOfKey从第二个节点往后找
//        // 如果找到就返回value值等于key节点的前一个节点
//        ListNode prev = findPrevOfKey(key);
//        if (prev == null) {
//            System.out.println("没有你要删除的数");
//        }else {
//            prev.next = prev.next.next;
//        }
//    }
//    // 4 找到并返回第一个value等于key节点的前一个节点
//    private ListNode findPrevOfKey(int key) {
//        ListNode cur = this.head;
//        while (cur.next != null) {
//            if (cur.next.value == key) {
//                return cur;
//            }
//            cur = cur.next;
//        }
//        return null;
    }

    //删除所有值为key的节点
    public void removeAllKey(int key) {
//        //法一:先用while处理开头有删除节点的情况
//        // 1 先处理开头节点value等于key的问题
//        while(this.head != null && this.head.value == key) {
//            this.head = this.head.next;
//        }
//
//        // 2 判断此时链表是否为空链表
//        // 注意要放在第一步的下面,不然可能出现本来不是空链表,删除后成为空链表的情况
//        // 若:head==null,则完成删除
//        if(this.head == null) {
//            return;
//        }
//
//        // 3 判断从第一个不是value等于key的节点开始,后面的节点
//        // 注意:此时head是第一个value不等于key的节点，
//        // 且prev肯定不为null. cur可能为null,cur为null则删除完成
//        ListNode cur = this.head.next;
//        ListNode prev = this.head;
//
//        // 注意:相当于双指针,prev永远是cur的左边一个节点,cur在右边
//        while(cur != null) {
//            if(cur.value == key) {
//                prev.next = cur.next;
//            }else {
//                // 重点：当cur的value！=key时，prev才能改变位置
//                // 因为cur.value==key时，cur已经指向了下一个节点，下个节点的value可能也是key
//                prev = cur;
//            }
//            cur = cur.next;
//        }

        // 法二：最后处理链表开头有删除节点的情况
        // 注意：也可以开头不用while处理，先把第二个节点及之后的value等于key的节点删掉
        // 最后再来解决头节点value是否等于key的问题
        // 1 判断是否为空
        if(this.head == null) {
            return;
        }
        // 2 删除除头节点外的value等于key的节点
        ListNode cur = this.head.next;
        ListNode prev = this.head;  //注意：prev记录cur左边最靠近一个value不等于key的节点,头节点是删除节点不算在内
        while(cur != null) {
            if(cur.value == key){
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        // 3 判断头节点value等于key的情况
        //注意：上面的代码删掉了除第一个节点为value的其它节点，最后处理第一个节点
        if(this.head.value == key) {
            this.head = this.head.next;
        }
    }
    //得到单链表的长度
    public int size() {
        int size = 0;
        ListNode cur = this.head;
        //注意：不能开头size=1且cur->next != null，如果是空链表就会出问题，除法再分类
        while( cur!= null) {
            size++;
            cur = cur.next;
        }
        return size;
    }
}
